Kotlin collections: List, Map and Set

上一篇的解答：答案是不一定，如果 Money 這個 class 的其中一個變數是 var ，或是他也用到了另外一個 class ，就會是 mutable 的（可以被修改）

class Account(val id: Int, val money: Money)
// amount 可能會被修改
class Money(var amount: Int, val currency: String)

接下來進入這這一篇應該是最多人會接觸到的部分，很多人是由 map、 filter 這些 operator 認識 functional programming 的。那麼，只要使用這些 operator 就代表我們真的在寫 functional programming 了嗎？還是看個例子比較快，先來看看 map 的用法吧：

Map

val numbers = listOf(1, 2, 3)
// numbers = [1, 2, 3]
val doubleNumbers = numbers.map { x -> x * 2}
// doubleNumbers = [2, 4, 6]

map 所做的事情就是將 list 裡的所有元素都拿出來計算，並建立出一個新的 List 來存放他。以下分幾個層面來探討：

為什麼叫做 map ?

對一個 Java 開法者來說，map 是一個非常熟悉的資料結構，常常用來解決空間換取時間的問題。以抽象一點的層面上來看，他的概念是一個 key 對應到一個 value ，而這個一對一的對應關係就是 map 。現在再回頭來看這個 operator ，其實他的概念也是一對一，只是他的對應關係變成了， 一組集合對應到了另一組集合。下面舉了其中幾種可能性

// Int 的集合 -> String 的集合
val stringNumbers = numbers.map { x -> x.toString() }
// Int 的集合 -> float 的集合
val divideNumbers = numbers.map { x -> x / 3f }
// Int 的集合 -> Point 的集合
val points = numbers.map { x -> Point(x, x + 1) }

map 的實作

既然我們都要學 functional programming 了，那實作也得要好好看懂才是：

public inline fun <T, R> Iterable<T>.map(transform: (T) -> R): List<R> {
    return mapTo(ArrayList<R>(collectionSizeOrDefault(10)), transform)
}

public inline fun <T, R, C : MutableCollection<in R>> Iterable<T>.mapTo(destination: C, transform: (T) -> R): C {
    for (item in this)
        destination.add(transform(item))
    return destination
}

恩....好像有點可怕，但是別擔心，我們來做點小小的簡化

fun <T, R> List<T>.map(transform: (T) -> R): List<R> {
    val destination = ArrayList<R>()        //1
    for (item in this)
				destination.add(transform(item))    //2
		return destination
}

看起來是不是簡單多了呢？你會發現很多特性在前面就有介紹過了： extension function、higher order function 以及泛型。這個 map 在做的事情就是：

(1) 建立一個新的 List - destination，並且

(2) 拿出來原來的 List 裡的每一個 item ，並拿來當作參數執給 transform 這個 function 去執行 ，再把得到的結果加到 destination 裡。

簡化過後的版本跟原來的版本比較起來，不一樣的地方有 Extension 的對象 Iterable 換成了 List，還有為了重用而抽取出來的函式 mapTo 與 collectionSizeOrDefault。那Iterable 是什麼呢？如果對 Java 夠熟的話就會知道他是很多“集合”類別的共同介面，像是 List、ArrayList、Set、Stack 等等。

這些類別都繼承了 Iterable ，只需要實作一次就能支援這麼多類別，超棒的不是嗎？但是不幸的是，這個優點也同時是他的缺點，再來看看以下這段程式：

val list: List<Int> = listOf(1, 2, 3)
val listMapping: List<Int> = list.map { x -> x + 1 }

val set: Set<Int> = setOf(1,2, 3)
val setMapping: List<Int> = set.map { x -> x + 2 }

發現了嗎？ Set 在經過 map 過後竟然變成了 List ！一般來說，我們會期望型別是不會被改變的，要嘛就是從頭到尾都是 List ，不然就是從頭到尾都是 Set ，當然我相信 Kotlin 這樣設計的背後是有他的理由的，但是這樣隱性（implicit） 的轉換應該會是很多人都不會預期到的。

接下來看看 Map 的 map 吧（好繞口）

val map: Map<String, Int> = mapOf("key" to 4)
// 1
val mapMapping: List<String> = map.map { (key, value) -> key + value }
// 2
val mapMappingValue: Map<String, Int> = map.mapValues { (key, value) -> value *2 }

可以看到

1. 即使是 Map ，經過 map operator 後還是轉換型態成 List 了。
2. 如果要的資料型別還是 Map 的話，就得要使用 mapValue 這個 operator （或是 mapKeys 也可以）。

至於具體實作的話就請各位自行研究了，懂了 Iterable 的實作之後不會太難才是。

Filter

一樣先舉個例子

val list: List<Int> = listOf(1, 2, 3)
// list = [1, 2, 3]
val oddList: List<Int> = list.filter { x -> x % 2 == 1 }
// list = [1, 3]
val evenList: List<Int> = list.filter { x -> x % 2 == 0 }
// list = [2]

從上面的例子就能很明顯的得知 filter 的用法，他能過濾不需要的 item ，只要在 lambda 裡寫出判斷的條件即可，條件為 true 的話，就會將該 item 留下來。至於內部實作長什麼樣子呢？有了之前的經驗，應該不難猜出這也是 extension function 跟 higher order function。話不多說，直接來看看這是怎麼看實作出來的吧！

public inline fun <T> Iterable<T>.filter(predicate: (T) -> Boolean): List<T> {
    return filterTo(ArrayList<T>(), predicate)
}

public inline fun <T, C : MutableCollection<in T>> Iterable<T>.filterTo(destination: C, predicate: (T) -> Boolean): C {
    for (element in this) if (predicate(element)) destination.add(element)
    return destination
}

跟 map 的實作非常像，對吧？最大的差異是帶進去的 lambda function type 從 (T) → R 變成了 (T) → Boolean，還有該 lambda 執行的位置：map 是執行在每個 item 上 ，filter 則是執行在 if 的判斷式裡。很一致的， filter 也直接實作在 Iterable 這個界面上，回傳的型別也是 List，上述的隱性型別轉換在這裡也發生了！那 Map 的 filter 又是長什麼樣子的呢？

val map: Map<String, Int> = mapOf("key" to 4)
// map.map 回傳的型別是 List<T>
val mapFilter: Map<String, Int> = map.filter { (key, value) -> value > 2 }
val mapFilterKey: Map<String, Int> = map.filterKeys { key -> key.length > 2 }
val mapFilterValue: Map<String, Int> = map.filterValues { value -> value > 2 }

驚呆了！回傳的型別不是 List 而是 Map！照理說應該要跟 map 這個 operator 的規則一樣不是比較好嗎？為什麼要改來改去的呢？

Function chaining

這在 function programming 中是一個非常常見的風格，簡單的來說，就是把不同的 operator 串在一起，寫的程式碼會少很多，閱讀起來也會相對順暢！

val set: Set<Int> = setOf(1, 2, 3, 4)
val setMapping: Set<Int> = set.map { x -> x + 2 }
    .filter { x -> x % 2 == 0 }
    .toSet()

在這個例子中我們把 map, filter, toSet 串在一起了，不用再每個都要有相對應的變數來儲存他。但是要注意！在每一個 operator 的計算中，都會產生一個新的 List ，不會因為沒有儲存成變數就不存在！

好了，讓我們先忘掉本篇所講的 map 以及 filter 的回傳型別，假裝你不知道他會回傳 List，再仔細看看上面這個範例，好像哪裏怪怪的，對吧！為什麼一個 Set 經由一連串操作過後還要再轉回成 Set ?難道不能每個步驟的型別都回傳 Set 嗎？

再談 composition

還記得 functional programming 其中的一個重要的元素 - composition 嗎？function chaining 看起來是不是也有點像是 composition 呢？在先前的範例中我們計算的是 Int, String 這種簡單的型別，在這裏只是換成了 Set, List, Map，如果是以這種角度來看的話，他們不都是做一樣的事嗎？

val addOne = {x: Int -> x + 1}
val divideTwo = {x: Int -> x/2}

// 還記得 pipe 嗎？忘了的話回去看第二篇吧！
val primitiveApproach = (addOne pipe divideTwo)(5)

val listChaining = listOf(5, 6, 7)
    .map(addOne)
    .map(divideTwo)

val listChaining2 = listOf(5, 6, 7)
    .map(addOne pipe divideTwo)

你可以把第二篇學的內容想像成是水平的 composition，連續兩個 map 則是垂直的 composition。有趣的事情來了，listChaining 跟 listChaining2 這兩種寫法是等價的嗎？看起來是等價的沒錯吧？然而你要怎證明他們是等價的呢？很有趣對吧！好吧，這些知識需要靠後面會介紹到 Category theory ，後面就會知道答案的。

還記得本篇一開始的問題嗎？使用 operator 是不是等於在寫 functional programming 呢？現在有更清楚的答案了嗎？如果沒有，在下一篇的 partial function 與下下一篇的 side effect 你將可以獲得更完整的答案。

小結

又到了實作時間了，本篇有提到說， Map 這個資料型別經由 map 這個 operator 之後，型別變成了 List ！現在想請讀者實作看看型別維持原樣的版本，如下：

val sample = mapOf(1 to "1", 2 to "2", 3 to "3")
val result: Map<Int, String> = sample.fmap { str -> str + "hello" }
println(result)        // {1=1hello, 2=2hello, 3=3hello}

請讀者實作看看這個 fmap 。另外提一下，Kotlin 著名的 functional programming library - Arrow，其實也有這種實作，回傳的型別跟原來的型別一致。以下附上連結：https://arrow-kt.io/docs/arrow/core/mapk/

最後的最後，Kotlin 鐵人陣中的團長剛好就是寫 Collection 的主題。想要了解其他延伸的主題，可以去多看看他的文章喔～
文章連結：https://ithelp.ithome.com.tw/users/20107229/ironman/3244